import javafx.util.Pair;

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int[] dx = new int[] {0, 0, 1, -1};
    public int[] dy = new int[] {1, -1, 0, 0};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int prevColor = image[sr][sc];
        if(prevColor == color){
            return image;
        }
        int m = image.length;//对应x
        int n = image[0].length;//对应y
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<Integer, Integer>(sr, sc));
        while(!queue.isEmpty()){
            Pair<Integer, Integer> pair = queue.poll();
            int a = pair.getKey();
            int b = pair.getValue();
            image[a][b] = color;
            for(int i = 0; i < 4; i++){
                int x = a + dx[i];
                int y = b + dy[i];
                if(x >= 0 && x < m && y >= 0 && y < n){
                    if(image[x][y] == prevColor){
                        queue.offer(new Pair<Integer, Integer>(x, y));
                    }
                }
            }
        }
        return image;
    }
}